Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Microsoft Medium Problems
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Multiply Strings

Problem Statement

Given two non-negative numbers num1 and num2 represented as strings, return the multiplication of num1 and num2 , represented as a string.

Examples

  • Example 1:

    • Input: num1: 4, num2: 5
    • Expected Output: "20"
    • Justification: Multiplying 4 by 5 gives 20, showcasing simple multiplication.
  • Example 2:

    • Input: num1: 11, num2: 11
    • Expected Output: "121"
    • Justification: The multiplication of 11 by 11 equals 121.
  • Example 3:

    • Input: num1: 999, num2: 999
    • Expected Output: "998001"
    • Justification: The multiplication of 999 by 999 equals 998001.

Solution

To solve this problem, the key is to mimic the traditional multiplication method we use by hand, where numbers are multiplied digit by digit and the intermediate results are added to get the final product. This approach is effective because it allows us to handle very large numbers that might not fit into standard data types. By iterating over each digit of both numbers starting from the least significant digit, we can ensure that every digit is accounted for in the multiplication process. The product of each pair of digits is placed at the correct position in the result array to handle carry and accumulation accurately.

This strategy is chosen because it does not rely on converting strings to integers, thus avoiding overflow or precision issues with very large numbers. It directly manipulates the strings and uses basic arithmetic principles to achieve the result. This method is both scalable and precise, making it the most suitable for our problem.

Step-by-Step Algorithm

  1. Initialize a result array of size num1.length + num2.length to hold the multiplication results, filled initially with zeros.
  2. Traverse both num1 and num2 from right to left (i.e., from the least significant digit to the most significant).
  3. For each digit in num1 (indexed by i) and num2 (indexed by j):
    • Multiply the digits at the current indices: (num1[i] - '0') * (num2[j] - '0').
    • Calculate the position in the result array where this product should be added: position1 = i + j and position2 = i + j + 1.
    • Add the product to result[position2], and manage any carry that results from this addition.
    • If there's a carry, add it to result[position1].
  4. Once all digits have been processed, the result array will contain numbers that might be more than 9 (except the last digit). Starting from the right, convert these to a single digit and carry over the remainder to the next left position.
  5. Finally, convert the result array to a string. If the string has leading zeros, remove them before returning the result.

Algorithm Walkthrough

Let's consider the input, num1: "999", num2: "999"

The result array has a length of num1.length + num2.length = 6, initially filled with zeros: [0, 0, 0, 0, 0, 0].

Iteration 1: i = 2, j = 2 (Both last digits)

  • Calculation: 9 * 9 = 81
  • Placement: Add 81, result becomes [0, 0, 0, 0, 8, 1].

Iteration 2: i = 2, j = 1 (Last digit of num1, second last of num2)

  • Calculation: 9 * 9 = 81
  • Placement with carry: Add to positions 3 and 4, considering carry from the previous step.
  • Result Array: [0, 0, 0, 8, 9, 1].

Iteration 3: i = 2, j = 0 (Last digit of num1, first digit of num2)

  • Calculation: 9 * 9 = 81
  • Placement with carry: Add to positions 2 and 3, considering carry from the previous step.
  • Result Array: [0, 0, 8, 9, 9, 1] (carries will be adjusted later).

Iteration 4: i = 1, j = 2 (Second last digit of num1, last digit of num2)

  • Calculation: 9 * 9 = 81
  • Placement with carry: Considering previous carries, add to positions 3 and 4.
  • Result Array: [0, 0, 8, 18, 0, 1].

Iteration 5: i = 1, j = 1 (Second last digits of both numbers)

  • Calculation: 9 * 9 = 81
  • Placement with carry: Add to positions 2 and 3.
  • Result Array: [0, 0, 17, 9, 0, 1].

Iteration 6: i = 1, j = 0 (Second last digit of num1, first digit of num2)

  • Calculation: 9 * 9 = 81
  • Placement with carry: Add to positions 1 and 2.
  • Result Array: [ 0, 9, 8, 9, 0, 1 ].

Iteration 7: i = 0, j = 2 (First digit of num1, last digit of num2)

  • Calculation: 9 * 9 = 81
  • Placement with carry: Add to positions 2 and 3.
  • Result Array: [ 0, 9, 17, 0, 0, 1 ].

Iteration 8: i = 0, j = 1 (First digits of num1, second last of num2)

  • Calculation: 9 * 9 = 81
  • Placement with carry: Add to positions 1 and 2.
  • Result Array: [ 0, 18, 8, 0, 0, 1 ].

Iteration 9: i = 0, j = 0 (Both first digits)

  • Calculation: 9 * 9 = 81
  • Placement with carry: Add to positions 0 and 1.
  • Result Array: [ 9, 9, 8, 0, 0, 1 ].

Converting to String:

  • Convert result array into a string "998001" and remove any leading zeros if present (not required in this case since the result does not start with zero).

Final Output:

  • The multiplication of "999" by "999" yields "998001" after adjusting the carries correctly in each step.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: , where m and n are the lengths of the two input strings. This is because each digit of both numbers needs to be multiplied with every digit of the other number.
  • Space Complexity: , required for the result array to store intermediate values. This is the maximum length the result can have.
Multiply Strings (medium)
Best Time to Buy and Sell Stock II (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis